Every computer and communication network which transfers data packets must implement some form of scheduling to insure that data traffic progresses through the network with a defined quality. At any given moment, a network may have hundreds of thousands or even millions of connections containing data queues waiting for transport through the network. Some form of scheduling is required to enable network elements to process these data queues in a fair and efficient manner.
A simple form of scheduling is a “First In-First Out” (“FIFO”) approach where the first packets received by a network device are the first packets distributed to a destination. A second scheduling method is known as a “round-robin” approach where each incoming data queue is assigned an equal dequeuing time slice and each queue is processed in turn by pulling data from the queue according to its assigned time. However, FIFO and round-robin scheduling do not allow for prioritization of data queues.
Generally, service providers sell network access to subscribers according to a guaranteed data service rate. Some service plans guarantee faster data delivery rates than others. Subscribers often pay a premium for higher guaranteed rates, while lower fees may apply to slower guaranteed rates. Additionally, service providers may selectively section off a portion of their available resources as dedicated to certain types of data that require more bandwidth and/or immediate delivery, e.g., streamed video, voice-over-IP (“VoIP”), etc. Service providers are able to implement structured pricing plans and guaranteed delivery of various data types by implementing priority values to incoming data. More advanced scheduling techniques take into consideration the assigned priority values when determining which data to dequeue, i.e., transmit.
For example, one form of scheduling is known as rate-based scheduling or shaping. Rate-based scheduling aims for specific data queues to be serviced, i.e., processed, according to a given data rate. The target data rate can be offered as a range of service rates having a minimum guaranteed rate, a maximum rate limit, and one or more burst quanta. A minimum guaranteed rate often refers to a contracted minimum bandwidth which must always be available, even when the network is very busy. A maximum rate often refers to a bandwidth limit that will be allowed to transmit (for more than a defined burst) and typically applies when the network is not busy. A distinct characteristic of rate scheduling is this behavior of limiting the transmitted bandwidth when the network could accept additional bandwidth. A scheduler assigns each connection to an incoming data queue with a specific service description. The scheduler then services the queues while respecting the service rates, without considering the overall queuing load.
Another form of scheduling is generally known as weighted fair queuing (“WFQ”). WFQ is a derivative of Fair Queuing wherein each data queue is serviced with a different share of the total bandwidth according to an assigned weight. WFQ in this context does not refer to a specific algorithm; it could refer to any algorithm which provides proportional fairness between queues.
Yet another form of scheduling is priority queuing (“PQ”). Priority queuing is a technique where a scheduler gives certain data queues preferential service over other data queues. Sometimes priority queuing schemes also incorporate service limits or service guarantees to avoid a situation where lower priority queues get no service for sustained periods.
A scheduling system may be represented according to a hierarchical tree structure 10, such as the one depicted in FIG. 1, wherein a root node (L1) typically represents the entire bandwidth of the network or data pipe. The root node is subdivided to child nodes L21 and L22 in which a child is allotted a portion of the total bandwidth according to its assigned weight W21 and W22. Each child node may be further subdivided into “grandchild” nodes, such as Q0 and Q1 for child L21, wherein the total share of the child node's bandwidth is divided among the grandchildren, and so on. The lowest nodes in this tree structure are sometimes referred to as “leaves” and generally represent data queues. Non-leaf nodes generally represent schedulers.
A scheduling system consisting of a hierarchical tree structure where each level runs a scheduling algorithm which attempts to partition bandwidth according to weights and priorities can generally be called a Hierarchical Weight-Based Scheduler (“HWS”). In one implementation of a HWS, a tree node may locally implement a mix of PQ and WFQ algorithms, such as scheduler L22 which is scheduling queue Q2 with high priority and partitioning the remaining bandwidth between queues Q3 and Q4 based on weight.
FIG. 2 shows another aspect important to HWS, which is the determination at all levels of the hierarchy of which children have data available (“DA”) to transmit. This aspect is called data available propagation. DA propagates from the leaves, i.e., queues, towards the root to announce changes of state from child to parent nodes. A first node propagates its data availability state to its parent when the first node is DA. The propagation puts the parent into the DA state, which may require further propagation to the grandparent if the parent was not previously DA. From the perspective of the parent, the parent non-leaf node is DA if at least one of its child nodes is DA. The overall effect of DA propagation is a node is DA if any of its descendant queues have data packets ready for delivery.
For example, node L1 is DA if node L21 is DA, or node L22 is DA. Node L21 is DA if either Q0 or Q1 is DA. At any time, if a node is not DA, its share of the bandwidth is divided amongst the remaining DA nodes according to their priorities and weights. Where a node has children with PQ configured, such as Q2 for node L22 which is a high priority queue, i.e., strict priority or equivalent to infinite weight), a proportional distribution of bandwidth based on weight fairness generally occurs after satisfying the priority children.
An HWS system, as defined here, provides a fair distribution of bandwidth based on priorities and weight values; however, network service providers often sell their services based on rate not proportional weight, e.g., subscriber rate may equal 1 Mb/sec. Under some network loads, rate based scheduling is more intuitive and/or required, e.g., lightly or heavily loaded networks, but under other network loads, weight-based scheduling with hierarchy is fairest. Some service providers have developed the ability to switch between a rate-based scheduler and an HWS scheduler depending upon network load or time of day. However, it is difficult to implement a combination of the two methods that work simultaneously.
Therefore, what is needed is a method and system for scheduling data packet transmission using a contemporaneous combination of rate scheduling and hierarchical weight-based scheduling.